class UnionFind {
  constructor(n) { // n表示图纸节点的个数
    this.count = n // 连通分量的个数
    this.parent = new Array(n) // 储存每个节点的父节点  下标代表节点的编号 值是节点的父节点
    for (let i = 0; i < n; i++) {
      this.parent[i] = i // 初始化每个节点的父节点都是自己本身
    }
  }
  union (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    if (rootP === rootQ) {
      return
    }
    this.parent[rootP] = rootQ // 让其中一个指向另一个的父节点
    this.count-- // 连通的分量减一  因为两个合成了一个了
  }
  connected (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    return rootQ === rootP // 找到两个的根节点 判断是不是相同
  }
  find (x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
  getCount () {
    return this.count // 返回连通量的个数
  }
}